package Set_and_Dict;

/*
直线上最多的点数
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：
输入：points = [[1,1],[2,2],[3,3]]
输出：3
示例 2：
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/all-about-lockup-table/xha3f7/
 */

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class _44直线上最多的点数 {
    public static void main(String[] args) {
        int[][] n = {{4,5},{4,-1},{4,0}};
        System.out.println(maxPoints(n));

    }

    //计算机除法的精度问题，导致代码出错
    //可以通过将除法转化为乘法，巧妙的解决本问题
    //或者采用二元法记录，即另类方法记录数据
    public static int maxPoints(int[][] points) {
        if (points == null || points.length == 0) return 0;
        if(points.length <= 2) return points.length;
        int n = points.length;
        HashMap<Double, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                double k = (double) y / x;
                if(x == 0 || y == 0)
                    k = Math.abs(k);
                map.put(k, map.getOrDefault(k, 0) + 1);
                max = Math.max(max, map.get(k));
            }
        }
        int res = (int)Math.sqrt(max) + 1;
        return res;
    }

    //宫水三叶
    //暴力枚举
    class Solution {
        public int maxPoints(int[][] points) {
            int n = points.length, ans = 1;
            for (int i = 0; i < n; i++) {
                int[] x = points[i];
                for (int j = i + 1; j < n; j++) {
                    int[] y = points[j];
                    // 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上
                    int cnt = 2;
                    for (int k = j + 1; k < n; k++) {
                        int[] p = points[k];
                        int s1 = (y[1] - x[1]) * (p[0] - y[0]);
                        int s2 = (p[1] - y[1]) * (y[0] - x[0]);
                        if (s1 == s2) cnt++;
                    }
                    ans = Math.max(ans, cnt);
                }
            }
            return ans;
        }
    }

    //官解
    //gcd  两个数的最大公约数
    class Solution2 {
        public int maxPoints(int[][] points) {
            int n = points.length;
            if (n <= 2) {
                return n;
            }
            int ret = 0;
            for (int i = 0; i < n; i++) {
                if (ret >= n - i || ret > n / 2) {
                    break;
                }
                Map<Integer, Integer> map = new HashMap<Integer, Integer>();
                for (int j = i + 1; j < n; j++) {
                    int x = points[i][0] - points[j][0];
                    int y = points[i][1] - points[j][1];
                    if (x == 0) {
                        y = 1;
                    } else if (y == 0) {
                        x = 1;
                    } else {
                        if (y < 0) {
                            x = -x;
                            y = -y;
                        }
                        int gcdXY = gcd(Math.abs(x), Math.abs(y));
                        x /= gcdXY;
                        y /= gcdXY;
                    }
                    int key = y + x * 20001;
                    map.put(key, map.getOrDefault(key, 0) + 1);
                }
                int maxn = 0;
                for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
                    int num = entry.getValue();
                    maxn = Math.max(maxn, num + 1);
                }
                ret = Math.max(ret, maxn);
            }
            return ret;
        }

        public int gcd(int a, int b) {
            return b != 0 ? gcd(b, a % b) : a;
        }
    }

}
